//每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {
        //单调栈 找右边第一个比栈顶元素大的元素
        stack<int>st;
        vector<int>answer(temperatures.size(),0);
        st.push(0);
        for(int i=1;i<temperatures.size();i++)
        {
            if(temperatures[i]<=temperatures[st.top()])
            {
                st.push(i);
            }
            else
            {
                while(!st.empty()&&temperatures[i]>temperatures[st.top()])
                {
                    answer[st.top()]=i-st.top();
                    st.pop();
               }
               st.push(i);
            }
        }
        return answer;
    }
};

//下一个更大元素II
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) 
    {
        //单调栈
        //找右边第一个比栈顶元素大的 遍历元素小于或者等于直接入栈即可
        stack<int>st;
        int n=nums.size();
        vector<int>result(nums.size(),-1);
        st.push(0);
        for(int i=1;i<nums.size()*2;i++)
        {
            if(nums[i%n]<= nums[st.top()]) st.push(i%n);
            else
            {
                while(!st.empty() && nums[i%n]>nums[st.top()])
                {
                    result[st.top()]=nums[i%n];
                    st.pop();
                }
                st.push(i%n);
            }
        }
        return result;
    }
};

//柱状图中最大的矩形
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        //单调栈
        //如果当前遍历的元素大于栈顶元素，那么以栈顶元素为高度的矩阵还可以继续
        //扩展，所以处理的逻辑是当当前遍历的元素小于了我的栈顶元素，那么以栈顶
        //元素为高的矩阵就不可能在更新了。
        //在heights数组中首元素插0的目的是 为了使 当出现需要更新res时，栈里至少有
        //三个元素 以便我走更新res的逻辑
        //尾部添加一个元素0的目的是，避免一直都找不到小于栈顶元素的值，导致程序走完
        //却没有更新res
        stack<int>st;
        int res=0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        st.push(0);
        for(int i=1;i<heights.size();i++)
        {
            if(heights[i]>=heights[st.top()]) st.push(i);
            else
            {
                while(!st.empty()&&heights[i]<heights[st.top()])
                {
                    int mid=st.top();
                    st.pop();
                    int left=st.top();
                    int h=heights[mid];
                    int d=i-left-1;
                    res=max(res,h*d);
                }
                st.push(i);
            }
        }
        return res;
    }
};

//实现Tire树
//Trie树 类似于多叉树 节点结构中有一个 可以表示所有字母的数组 _next 
//想要在Trie树中查询有没有当前单词 就从根节点 _head 的_next开始找字母
//找到一个 就让cur节点往下走一层 如果字符遍历完成，不一定就代表之前存过
//这个单词 可能是之前存的长单词中 包含了本次的单词，所以需要一个isEnd标记位
//标记以当前节点结束的单词 是不是存在的
struct TrieNode
{
    bool _isEnd;//每个节点 都可能是单词的结尾位置 用于标记
    TrieNode* _next[26];//保存了对当前节点而言 下一个可能出现的所有字符的链接
    TrieNode()
    {
        _isEnd=false;
        memset(_next,0,sizeof(_next));
    }
};
class Trie {
public:
    Trie() 
    {
        _head=new TrieNode();
    }
    
    void insert(string word) 
    {  
        TrieNode* cur=_head;
        for(auto ch:word)
        {
            if(cur->_next[ch-'a']==nullptr)
            {
                cur->_next[ch-'a']=new TrieNode();
            }
            cur=cur->_next[ch-'a'];
        }
        cur->_isEnd=true;
    }
    
    bool search(string word) 
    {
        TrieNode* cur=_head;
        for(auto ch:word)
        {
            if(cur->_next[ch-'a']==nullptr) return false;
            cur=cur->_next[ch-'a'];
        }
        if(cur->_isEnd==true) return true;
        else return false;
    }
    
    bool startsWith(string prefix) 
    {
        TrieNode* cur=_head;
        for(auto ch:prefix)
        {
            if(cur->_next[ch-'a']==nullptr) return false;
            cur=cur->_next[ch-'a'];
        }
        return true;
    }
private:
    TrieNode* _head;
};
